//
//  42.和为S的两个数字.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/27.
//

import Foundation
/*
 题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 思路：双指针
 */
func offer_42() {
    print(Solution().findNumbersWithSum([1,2,4,7,11,15],15))
}

fileprivate class Solution {
    func findNumbersWithSum(_ array: [Int],  _ sum: Int) -> [Int] {
        guard !array.isEmpty else { return [] }
        var result = [Int]()
        var left = 0
        var right = array.count - 1
        var temp = Int.max
        while left < right {
            if array[left] + array[right] > sum {
                right -= 1
            } else if array[left] + array[right] < sum {
                left += 1
            } else {
                if array[left] * array[right] < temp {
                    temp = array[left] * array[right]
                    result = [array[left], array[right]]
                }
                left += 1
                right -= 1
            }
        }
        return result
    }
}



